#include <iostream>
#include <vector>
#include <stack>

using namespace std;


class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        unsigned long size = heights.size();
        if (size == 1) return heights[0];

        int i = 0, top = 0, s = 0, s_max = 0;
        stack<int> stk;
        while (i < size) {
            if (stk.empty() || heights[i]>heights[stk.top()]) {
                stk.push(i++);
            } else {
                top = stk.top(); stk.pop();
                s = heights[top] * (stk.empty() ? i : i-stk.top()-1);
                s_max = max(s, s_max);
            }
        }
        
        while (!stk.empty()) {
            top = stk.top(); stk.pop();
            s = heights[top] * (stk.empty() ? size : size-stk.top()-1);
            s_max = max(s, s_max);
        }

        return s_max;
    }
};


int main(void) {
    // Test cases
    vector<int> v1 = {1};
    vector<int> v2 = {2,1,5,6,4};
    vector<int> v3 = {1,2,5,2,1,5,5};
    vector<int> v4 = {4,2,0,3,2,4,3,4};

    Solution soln = Solution();
    cout << soln.largestRectangleArea(v1) << endl;
    cout << soln.largestRectangleArea(v2) << endl;
    cout << soln.largestRectangleArea(v3) << endl;
    cout << soln.largestRectangleArea(v4) << endl;
    return 0;
}
